import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网: BM92 最长无重复子数组
 * User: DELL
 * Date: 2023-08-16
 * Time: 23:16
 */
public class Solution {
    /**
     * 解题思路: (双指针+哈希)
     * 首先题目中要求的是连续的最长的无重复子数组，不是连续最长的递增或递减数组，因此这里首先想到
     * 的就应该是哈希，即将数组中的元素做一下哈希，将 key 设定为数组中元素的值，将 value 设定为
     * 元素对应的下标。
     * 那么既然要求的是连续的最长无重复数组，因此其中可能会有重复的 key，因此如何合理处理这些重复
     * 的 key 成为了关键。这里我想的方法如下:
     * 首先定义一个变量 maxLen，记录最长的无重复数组的长度，同时定义变量 leftIndex 来记录当前
     * 最长的没有重复元素数组的左下标。
     * 然后开始遍历数组 arr，遍历的时候，若当前元素的值没有出现过，那么直接将当前元素和当前元素的
     * 下标哈希一下即可；而如果当前元素的值出现过，那么就先看前一次出现的数组下标，若前一次出现的
     * 数组的下标小于 leftIndex，即对当前数组没影响，直接将当前元素的 value 改为当前下标即可，
     * 而若前一次出现的数组的下标大于等于 leftIndex，即说明在当前数组中出现了重复，那么当前数组
     * 的最长无重复数组的长度即为 i - leftIndex，这时维护 maxLen，即
     * maxLen = Math.max(maxLen,i-leftIndex)，同时将当前元素的 value 改为当前下标即可。
     * 最后返回值返回 Math.max(maxLen,arr.length-leftIndex) 即可，即因为最后一个无重复
     * 子数组没算进去，因此在最后注意一下即可。
     * 总体思路就是上面，较难理解，若不好理解，可以画个图会更好理解。
     *
     * 另外还有就是利用队列来解题，即从左到右，依次将 arr 中的元素放入队列中，若出现重复，则将
     * 重复点之前的元素，均出队列，同时维护一个变量记录最大长度即可，其实本质思路都是一样的，
     * 上面的方法其实就是这个方法的另一种形式，即通过哈希来减少了判断重复元素所消耗的时间，效率
     * 更高。
     * @param arr
     * @return
     */
    public int maxLength (int[] arr) {
        // 判空处理
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int maxLen = 0;
        int leftIndex = 0;
        // k 为数组中元素的值  v 为该元素对应的下标
        Map<Integer,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (!hashMap.containsKey(arr[i])) {
                hashMap.put(arr[i],i);
            } else {
                if (hashMap.get(arr[i]) < leftIndex) {
                    hashMap.put(arr[i],i);
                } else {
                    maxLen = Math.max(maxLen,i-leftIndex);
                    leftIndex = hashMap.get(arr[i])+1;
                    hashMap.put(arr[i],i);
                }
            }
        }
        return Math.max(maxLen,arr.length-leftIndex);
    }
}